import { swap, randomIndex } from './utils'
function partition (arr, L, R) {
  // 以arr[R]作为num划分
  let less = L - 1
  let more = R + 1
  while (L < more) {
    if (arr[L] < arr[R]) {
      swap(arr, L++, ++less)
    } else if (arr[L] > arr[R]) {
      swap(arr, L, --more)
    } else {
      L++
    }
  }
  return [less + 1, more - 1] // 返回等于区域的下标
}

function _sort (arr, L, R) {
  if (L >= R) {
    return
  }
  swap(arr, randomIndex(L, R), R) // 随机交换一次
  const [p1, p2] = partition(arr, L, R)
  _sort(arr, L, p1 - 1)
  _sort(arr, p2 + 1, R)
}

function quickSort (arr) {
  if (arr == null || arr.length < 2) {
    return
  }
  _sort(arr, 0, arr.length - 1)
}

const arr2 = [9, 5, 2, 3, 1, 8, 7, 5, 6, 5, 4, 5, 3, 2, 1]
quickSort(arr2)
console.log(arr2)
